package nowcoder.offer;

import jdk.nashorn.internal.runtime.arrays.ArrayLikeIterator;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 按之字形打印二叉树
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-29 19:48
 */
public class PrintZ {

    public ArrayList<ArrayList<Integer>> solution(TreeNode pRoot){
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot == null) return res;
        int row = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        while (!queue.isEmpty()){
            LinkedList<TreeNode> deque = new LinkedList<>();
            while (!queue.isEmpty()) {
                deque.offer(queue.poll());
            }
            if (row % 2 ==0){
                ArrayList<Integer> list = new ArrayList<>();
                while (!deque.isEmpty()){
                    TreeNode node = deque.poll();
                    if (node.left != null) queue.offer(node.left);
                    if (node.right != null) queue.offer(node.right);
                    list.add(node.val);
                }
                res.add(list);
                row++;

            }else {
                ArrayList<Integer> list = new ArrayList<>();
                while (!deque.isEmpty()){
                    TreeNode node = deque.pollLast();
                    if (node.right != null) queue.offerFirst(node.right);
                    if (node.left != null) queue.offerFirst(node.left);
                    list.add(node.val);
                }
                res.add(list);
                row++;
            }
        }


        return res;
    }


    public ArrayList<ArrayList<Integer>> solution2(TreeNode pRoot){
        ArrayList<ArrayList<Integer>>  res = new ArrayList<>();
        if (pRoot == null) return res;

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        int row = 0;
        while (!queue.isEmpty()) {

            LinkedList<TreeNode> nodes = new LinkedList<>();
            int len = 0;
            while (!queue.isEmpty()){
                nodes.offer(queue.poll());
            }
            LinkedList<Integer> list = new LinkedList<>();
            while (!nodes.isEmpty()) {
                TreeNode node = nodes.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
                if (row % 2 != 0) list.offerFirst(node.val);
                else list.offer(node.val);
            }

            row++;
            res.add(new ArrayList<>(list));
        }

        return res;
    }




    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(7);

        root.right = new TreeNode(10);
        root.right.left = new TreeNode(9);
        root.right.right = new TreeNode(11);

        new PrintZ().solution2(root);
    }
}
